1. Field of Invention
The present invention relates to network communications. The present invention is more particularly related to buffers and the processes of saving and retrieving data from the buffer. The present invention is still more particularly related to accelerating packet buffer operations for a high speed network interface device.
2. Discussion of Background
Although this specification presumes familiarity with the general concepts, protocols, and devices commonly used in LAN networking applications, each of which have corresponding standards that are publicly available, (e.g., the IEEE 802.3 standard (Ethernet)), a brief overview is provided.
General Network Topology
Local area networks (LANs) are arrangements of various hardware and software elements that operate together to allow a number of digital devices to exchange data within the LAN and also may include internet connections to external wide area networks (WANs). FIG. 1 is a diagram representing a modern LAN 100 comprised of one to many Hosts or End Systems (ESs) such as hosts 1 . . . n that are responsible for data transmission throughout the LAN. The ESs may be familiar end-user data processing equipment such as personal computers, workstations, and printers and additionally may be digital devices such as digital telephones or real-time video displays. Different types of ESs can operate together on the same LAN. In FIG. 1, the hosts 1 . . . n are on a ring type LAN having a server/bridge/router device 130, that may also be referred to as an Intermediate System (IS), that serves various network functions for the LAN 100, and administers each of a bridge to an attached LAN 160 and a router to a Wide Area Network (WAN) 190. However, modern networks may be composed of any number of hosts, bridges, switches, hubs, routers, and other network devices, and may be configured as any one or more of ring, star, and other configurations.
Packets
In a LAN such as 100, data is generally transmitted between ESs as independent packets, with each packet containing a header having at least a destination address specifying an ultimate destination and generally also having a source address and other transmission information such as transmission priority. Packets are generally formatted according to a particular protocol and contain a protocol identifier of that protocol. Packets may be encased in other packets.
Layers
Modern communication standards, such as the TCP/IP Suite and the IEEE 802 standards, organize the tasks necessary for data communication into layers. At different layers, data is viewed and organized differently, different protocols are followed, different packets are defined and different physical devices and software modules handle the data traffic. FIG. 2 illustrates various examples of layered network standards having a number of layers. Corresponding levels of the various network standards are shown adjacent to each other and the OSI layers, which are referred to herein as: the Physical Layer, the Data Link Layer, the Routing Layer, the Transport Layer, the Session Layer, the Presentation Layer and the Application Layer, are also shown for reference. Please note the TCP/IP protocol layers shown.
Generally, when an ES is communicating over a network using a layered protocol, a different software module may be running on the ES at each of the different layers in order to handle network functions at that layer.
Drivers and Adapters
Each of the ISs and ESs in FIG. 1 includes one or more adapters and a set of drivers. An adapter generally includes circuitry and connectors for communication over a segment and translates data from the digital form used by the computer circuitry in the IS or ES into a form that may be transmitted over the segment, which may be electrical signals, optical signals, radio waves, etc. A driver is a set of instructions resident on a device that allows the device to accomplish various tasks as defined by different network protocols. Drivers are generally software programs stored on the ISs or ESs in a manner that allows the drivers to be modified without modifying the IS or ES hardware.
NIC Driver
The lowest layer adapter software operating in one type of network ES is generally referred to as a NIC (Network Interface Card) driver. A NIC driver is layer 2 software designed to be tightly coupled to and integrated with the adapter hardware at the adapter interface (layer 1) and is also designed to provide a standardized interface between layer 2 and 3. Ideally, NIC drivers are small and are designed so that even in an ES with a large amount of installed network software, new adapter hardware can be substituted with a new NIC driver, and all other ES software can continue to access the network without modification.
NIC drivers communicate through one of several available NIC driver interfaces to higher layer network protocols. Examples of NIC driver interface specifications are NDIS (Network Driver Interface Specification developed by Microsoft and 3Com) and ODI (Open Data-Link Interface developed by Apple Computer and Novell).
Protocols
Ethernet is logical communication protocol that permits multiple devices to talk to each other over a variety of physical media. The Ethernet protocol is described in the IEEE 802.3 standard and utilizes a protocol called Carrier Sense Multiple Access with Collision Detection (CSMA/CD). CSMA/CD is a broadcast mechanism where one station speaks while all others listen. When two stations try to speak at the same time, a collision takes place. With CSMA/CD, both stations detect the collision, back off, and retry later.
A simple form of an Ethernet local area network (LAN) is illustrated by an Ethernet LAN in FIG. 3. A LAN adapter 310 provides the interface between a host 300 and an Ethernet transceiver 320, also called a medium attachment unit (MAU). The MAU 320 provides a physical interface to a LAN medium 330. An interface between the LAN adapter 310 and transceiver 320 is the adapter unit interface (AUI) 315. The Ethernet (LAN) medium 330 is normally a cable. The type of cable depends on the type of Ethernet. In many cases, a single electronics board combines the LAN adapter 310 and the transceiver 320 as LAN Adapter 340.
Table 1 provides the Ethernet/IEEE802 Packet Format:
TABLE 1MACIP headerTCP headerPayloadCRCheader
The Ethernet protocol runs on top of and therefore contains the TCP/IP protocol. The Media Access Control (MAC) header contains a MAC number that is a unique address of a host or other device connected to the LAN (NIC, for example). Although Ethernet is a popular protocol, other protocols are also in common use.
The TCP/IP (Transmission Control Protocol/Internet Protocol) protocol is a suite of protocols and is the standard for connection based data transmission and services across the Internet. The Transmission Control Protocol manages the packaging of data into packets that get routed on different paths over the Internet and reassembled at their destination. The Internet Protocol handles the address part of each data packet so that it is routed to the correct destination.
TCP re-assembly is the task performed for identifying and routing an incoming packet received at a host. Traditionally, the tasks of TCP re-assembly have been performed either by a host CPU or an embedded processor. In either case, to carry out this task, the CPU has to first identify which TCP connection the incoming packets belong to. It then extracts certain fields off of TCP/IP headers of the incoming packets to identify the sequence of the received payload within a current segment data file. To carry out these tasks, the CPU, or embedded processor, accesses a packet data buffer to retrieve packet header data and process the TCP/IP headers as required. In addition, outgoing packets may also be processed using a Transmission (Tx) packet buffer.
A typical packet buffer is organized in a conventional memory space. Table 2 provides an example organization of conventional memory for an n-byte, word, or double word set of memory locations.
TABLE 2byte 0byte 1byte 2byte 3byte 4byte 5...byte n-2byte n-1
In today's high speed networking such as Gigabit Ethernet or 10 Gigabit Ethernet, the overall throughput or performance suffers because packets cannot be processed as quickly as needed to keep up with the incoming data rates. Among other causes, a large amount of time is spent storing and accessing packets to/from the packet buffers and any improvements in speed or efficiency of packet buffer storage/retrieval is needed.